package LeetCode._02_数组;

public class _322_零钱兑换 {
    public int coinChange(int[] coins, int amount) {
        if(amount<1 || coins == null || coins.length == 0) return 0;
        int[] dp = new int[amount+1]; //结果数组
        for(int i=1;i<=amount;++i){
            int min = Integer.MAX_VALUE;
            for (int face : coins) {
                if(i<face) continue; //当前数小于面值
                if(dp[i-face]<0 || dp[i-face]>=min) continue;//凑够i分已经够了，就不需要在凑了
                min = dp[i-face];
            }
            //最小值的不合法情况
            if(min == Integer.MAX_VALUE){
                dp[i] = -1;
            }else{ //面值加1
                dp[i] = min + 1;
            }
        }
        return dp[amount];
    }
}
